
import java.io.*;
import java.util.*;

/**
 * Contains the main method and the 'Prim' method, along with other needed helper methods.
 * 
 * @author Ken "David" McClain
 * @version 20 May 2011
 */
public class Prim {
  
  /** Constant that represents infinity. 
    * This number should be greater than the largest edge weight multiplied by the number of vertices - 1 */
  public static final int INFINITY = 999999;
  
  /** Prim's algorithm in Java.
    * This method will run Prim's algorithm and select the shortest path.
    * The 'graph' object will not be changed, but the Vertex objects contained in Graph will contain
    * information about the shortest path.  Each Vertex contains a "VertexInfo" object as the "data" field.
    * The VertexInfo object tells:
    * - The distance from the Start vertex to this vertex.
    * - The previous vertex in the path.
    * 
    * @param graph The SimpleGraph containing vertices and edges.
    **/
  public static void Prim(SimpleGraph graph) {
    
    // Initialize heap with capacity |V|
    BinaryHeap heap = new BinaryHeap(graph.numVertices());
    
    // Flag for selecting the 'first' vertex as the start vertex
    boolean chosenFirst = false;
    
    // Iterate over every vertex, initialize them
    Iterator it = graph.vertices();
    while (it.hasNext()) {
      Vertex v = (Vertex) it.next();
      
      // If this is the first vertex encountered,
      if (!chosenFirst) {
        chosenFirst = true; // Set the flag
        // Mark this vertex's distance as '0' (since it's the start)
        v.setData(new VertexInfo(false, 0, null));
        System.out.println("Starting at vertex " + v.getName().toString());
      } else {
        // For all other vertices, mark the distance as INFINITY
        v.setData(new VertexInfo(false, INFINITY, null));
      }
      
      // Insert every vertex onto the heap
      heap.insert(new PrimHeapNode(v));
    }
    
    // Keep track of the total cost of path.
    double totalCost = 0.0;
    
    // This will loop until all vertices in the graph are known.
    while (true) {
      
      Vertex v = null;
      try {
        v = heap.deleteMin().v; // smallest unknown dist. vert;
      } catch (EmptyHeapException e) {}
      
      // 'v' is null if there are no more unknow vertices.
      if (v == null)
        break; // We are done.
      
      // We will be accessing the VertexInfo object for 'v' often.
      // Storing this as a variable makes the code much more readable.
      VertexInfo vi = (VertexInfo) v.getData();
      vi.setKnown(true);
      
      if (vi.getPrev() != null) {
        // print out edge from v to vi.prev
        System.out.println("Chosen edge from " + v.getName().toString() + " to " + vi.getPrev().getName().toString() + ", Cost: " + Double.parseDouble(vi.getPrevEdge().getData().toString()));
        
        // add cost of edge from v to vi.prev to totalCost
        totalCost += Double.parseDouble(vi.getPrevEdge().getData().toString());
      } else {
        // First vertex does not have previous vertex.
      }
      
      // Iterate over every neighbor of v
      it = graph.incidentEdges(v);
      while (it.hasNext()) {
        Edge e = (Edge) it.next();
        Vertex w = graph.opposite(v, e); // Use "opposite" to find the neighboring vertex
        
        // Store this object as a variable so we don't have to cast it repeatedly.
        VertexInfo wi = (VertexInfo) w.getData();
        
        // If 'w' is unknown...
        if (!wi.getKnown()) {
          // If v.dist + cvw < w.dist then
          if (vi.getDist() +  Double.parseDouble(e.getData().toString()) < wi.getDist()) {
            
            // Change w's distance to the new smaller distance
            wi.setDist(vi.getDist() + Double.parseDouble(e.getData().toString()));
            
            // Leave 'breadcrumbs' so we can figure out shortest path later.
            wi.setPrev(v);
            wi.setPrevEdge(e);
            
            // Update the heap (by ONLY percolating up w's index).
            heap.decrease(wi.getIndex());
          }
        }
        
      } // end of neighbor-iterating while loop
      
    }
    
    System.out.println("Total cost: " + totalCost);
  }
  
  /** Main method.
    * @param args Command line arguments. */
  public static void main(String[] args) {
    
    System.out.println("Prim's Algorithm.\n");
    System.out.println("Proper usage: java Prim [file]\n\n");
    
    if (args.length == 0) {
      System.out.println("Please enter the filename of the test path file.");
      System.exit(0);
    }
    
    SimpleGraph G;
    G = new SimpleGraph();
    
    // Read the graph from the command-line argument.
    Hashtable ht = GraphInput.LoadSimpleGraph(G, args[0]);
    
    Prim(G);
    
    // 
  }
}